package com.zhugang.week07;

/**
 * @program algorithms
 * @description: lowestCommonAncestor
 * @author: chanzhugang
 * @create: 2022/07/22 22:54
 */
public class LowestCommonAncestor {

    /**
     * 236 二叉树的最近公共祖先
     *
     * @param root
     * @param p
     * @param q
     * @return
     */

    private TreeNode lca = null;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 回溯解法之后会讲
        // 递归 ：找规律为 左子树包含p/q；右子树包含p/q
        dfs(root, p, q);
        return lca;
    }

    /**
     * 后序遍历：包含多少个p/q
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    private int dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return 0;
        }
        int leftContains = dfs(root.left, p, q);
        if (lca != null) {
            // 提前退出
            return 2;
        }
        int rightContains = dfs(root.right, p, q);
        if (lca != null) {
            return 2;
        }
        int rootContains = 0;
        if (root == p || root == q) {
            // 节点是自己的祖先
            rootContains = 1;
        }
        if (rootContains == 0 && leftContains == 1 && rightContains == 1) {
            // 左右子树分别包含p/q
            lca = root;
        }
        if (rootContains == 1 && (leftContains == 1 || rightContains == 1)) {
            // 根节点包含 或者 左右子树其中一个包含
            lca = root;
        }
        return leftContains + rightContains + rootContains;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}